Graph partitioning is a well known classical problem with many applications. For example, graph partitioning may be used with applications on road networks that include distributed preprocessing of routing information, real-time traffic route planning, and metric-independent route planning, as well as other applications that are unrelated to route planning. Known software libraries (e.g., METIS, SCOTCH, JOSTLE, etc.) solve the problem but the quality of the obtained solutions is often unacceptable on road networks.
More particularly, partitioning a graph into many well-separated cells is a fundamental problem in computer science with applications in areas such as VLSI design, computer vision, image analysis, distributed computing, and route planning. Most variants of this problem are known to be NP-hard (non-deterministic polynomial-time hard) and focus on minimizing the number of edges linking vertices from different cells (the “cut size”). There is much literature on the problem, including many heuristic solutions.
A popular approach is multilevel graph partitioning (MGP), which generally works in three phases. During the first phase, the graph is iteratively shrunk by contracting edges. This is repeated until the number of remaining vertices is small enough to perform an expensive initial partitioning (the second phase of MGP). At the third phase, the graph is partially uncontracted, and local search is applied to improve the cut size.
Although MGP approaches can be used for road networks, they do not exploit the natural properties of such networks in full. In particular, road networks are not uniform: there are densely populated regions (which should not be split) close to natural separators like bridges, mountain passes, and ferries. Moreover, known MGPs focus on balancing the sizes of the cells while sacrificing either connectivity or cut size. This makes sense for more uniform graphs, such as meshes. However, many road network applications use cells that are connected and one does not want to sacrifice the cut size. Such applications include route planning, distribution of data, and computation of centrality measures.